//****************************************************************
// Autor:   Gustavo Castro
//       
// Seccion: 10
// Nombre del Archivo: VectorHeap.java
// Fecha de Modificacion: 
// Descripcion:
// Código obtenido del libro de clase  
// pero se implementaron nuevos metodos: isGreater y it (iterator). 
// Se implementa un heap por medio de un Vector
// ***************************************************************

package hojatrabajo6;

import java.util.Iterator;
import java.util.Vector;

/**
 *
 * @author cristian
 */
public class VectorHeap implements PriorityQueue {
     protected Vector data;  // the data, kept in heap order

    public VectorHeap()
    {
	data = new Vector();
    }
    public VectorHeap(Vector v)
    {
	int i;
	data = new Vector(v.size()); // we know ultimate size
	for (i = 0; i < v.size(); i++)
	{   // add elements to heap
	    add((Comparable)v.get(i));
	}
    }
    protected static int parent(int i)
        {
	return (i-1)/2;
    }
    protected static int left(int i)
    {
	return 2*i+1;
    }
    protected static int right(int i)
    {
	return 2*(i+1);
    }
    public Comparable getFirst()
    {
	return (Comparable)data.get(0);
    }
    public Comparable remove()
    {
        Comparable minVal = getFirst();
	data.set(0,data.get(data.size()-1));
	data.setSize(data.size()-1);
	if (data.size() > 1) pushDownRoot(0);
	return minVal;
    }
    public void add(Comparable value)
    {
	data.add(value);
	percolateUp(data.size()-1);
    }
    protected void percolateUp(int leaf)
    {
	int parent = parent(leaf);
	Comparable value = (Comparable)(data.get(leaf));
	while (leaf > 0 &&
	 (value.compareTo((Comparable)(data.get(parent))) < 0))
	{
	    data.set(leaf,data.get(parent));
	    leaf = parent;
	    parent = parent(leaf);
	}
	data.set(leaf,value);
    }
    protected void pushDownRoot(int root)
    {
	int heapSize = data.size();
	Comparable value = (Comparable)data.get(root);
	while (root < heapSize) {
	    int childpos = left(root);
	    if (childpos < heapSize)
	    {
		if ((right(root) < heapSize) &&
	          (((Comparable)(data.get(childpos+1))).compareTo
    	           ((Comparable)(data.get(childpos))) < 0))
                {
		    childpos++;
		}
		// Assert: childpos indexes smaller of two children
		if (((Comparable)(data.get(childpos))).compareTo
		    (value) < 0)
		{
		    data.set(root,data.get(childpos));
		    root = childpos; // keep moving down
		} else { // found right location
		    data.set(root,value);
		    return;
		}
	    } 
            else { // at a leaf! insert and halt
		data.set(root,value);
		return;
	    }	    
	}
    }
    public boolean isEmpty()
    {
	return data.size() == 0;
    }
    
    public boolean isGreater(int num){
        return data.size()>num;
    }
    public Iterator it(){
        return data.iterator();
    }
    
}
